COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "memo.pub[let,jmc]" source
C00004 ENDMK
C⊗;
.require "memo.pub[let,jmc]" source
.turn on "→"
CS206∂(30)MIDTERM EXAMINATION→FALL 1977

	This examination is open book and notes.
Write LISP functions as follows except where something else is
requested.  Either notation may be used.
.item←0

#. %2depth x%1 is the length of the longest %2car-cdr%1 chain
reaching an atom in the S-expression ⊗x. 

#. Let ⊗u be a list, ⊗f a function on list elements and ⊗p a predicate
on list elements.  ⊗mapcat[u,f,p] is the obtained by appending elements
⊗f[x] of ⊗u such that ⊗p[x] is satisfied.

#. Let ⊗g be a directed graph in notation described in the notes.  (It is
a list of sublists, each sublist consisting of a vertex followed
by the vertices to which it is connected.  %2component[x,g]%1 is
a list of the vertices which may be reached from the vertex ⊗x by
a path in the graph.  %2bigcomponent[x,g]%1 is a list of all the
vertices to which ⊗x is connected by any combination of paths.

#. Let %2successors x%1 be the list of successors of an element ⊗x in
some search space, i.e. they are the elements of the space that can
be reached from ⊗x in one move.  %2bsearch[x,p]%1 is an element of
the space satisfying the predicate ⊗p and at the lowest depth in
the tree.